/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-ladder-ii
   @Language: C++
   @Datetime: 17-03-29 16:09
   */

class Solution {
	void traceDFS(unordered_map<string, unordered_set<string> > &trace
			,string last,vector<string> path
			,vector<vector<string> > &result) {
		path.push_back(last);
		if (trace.find(last)==trace.end()) {
			vector<string> temp = path;
			reverse(temp.begin(), temp.end());
			result.push_back(temp);
			return;
		}
		for(const auto &word:trace[last])
			traceDFS(trace,word,path,result);
	}

public:
	/**
	 * @param start, a string
	 * @param end, a string
	 * @param dict, a set of string
	 * @return a list of lists of string
	 * Tip: Using hash set to store next words, not queue
	 *      after current level traversal, delete visited words
	 *      Using Multi-Tree to store path (trace)
	 *      Using DFS to record path.
	 */
	vector<vector<string> > findLadders(string start, string end
			, unordered_set<string> &dict) {
		// write your code here
		if (start==end) return {{start}};
		unordered_map<string,unordered_set<string> > trace;
		unordered_set<string> levels[2];	// deal duplication
		int level = 0;
		for(levels[level].insert(start); levels[level].size(); level=!level){
			if (trace.find(end)!=trace.end()) break;
			for(const auto &word:levels[level])
				dict.erase(word);		// delete visited word
			levels[!level].clear();
			for(const auto &str:levels[level]){
				for(int j=0; j<str.length(); ++j){
					string s=str;           // preserve str
					for(char c='a'; c<='z'; ++c){
						if(str[j]==c) continue;   // skip
						s[j] = c;
						if(s!=end && dict.find(s)==dict.end()) continue;
						trace[s].insert(str);
						levels[!level].insert(s);
						// dict.erase(s), don't, may have same part-path
					}
				}
			}
		}
		// recovery trace back - DFS
		vector<vector<string> > result;
		traceDFS(trace,end,{},result);
		return result;
	}
};
